package com.lht.leetcodeDemo;

import org.junit.Test;

import java.util.*;

/**
 * @author Eric
 * @version 1.0
 * @date 2019-05-21
 */
public class IndexOf {

    @Test
    public void testRandom(){
        Random random=new Random();
        System.out.println(random.nextInt(1000));
        System.out.println(random.nextInt(25));
    }

    private Map<String, String> map = new LinkedHashMap<>(16);
    private List<String> strList=new ArrayList<>();

    {
        String englist="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
        map.put("mississippi", "issi");
        map.put("hello", "ll");
        map.put("babbbbbabb", "bbab");
        map.put("aaaaa", "bba");
        map.put("a", "a");
        map.put("mississippi", "issip");
        map.put("ababcaababcaabc","ababcaabc");



        Random random=new Random();
        StringBuilder sb=new StringBuilder();
        for(int i=0;i<1000000;i++){
            /*
                1. new StringBuilder 对象
                2. sb.delete(0,length)     效果最好
                3. sb.setLength(0)         效果其次
             */
            sb.delete(0,sb.length());
            int len=random.nextInt(1000);
            while(len/10>0){
                sb.append(englist.charAt(random.nextInt(25)));
                len=len/10;
            }
            strList.add(sb.toString());
        }

        strList.add("ababcaabc");

    }

    @Test
    public void testAllIndexOf() {

        map.forEach((k, v) -> {
            System.out.println("目标字符串:" + k + "，target字符串：" + v + ",结果：" + new IndexOf().indexOf(k, v));
        });
        map.forEach((k, v) -> {
            System.out.println("目标字符串:" + k + "，target字符串：" + v + ",结果：" + new IndexOf().kmpIndexOf(k, v));
        });
        map.forEach((k, v) -> {
            System.out.println("目标字符串:" + k + "，target字符串：" + v + ",结果：" + new IndexOf().bfIndexOf(k, v));
        });
    }

    /**
     * <p>
     * 暴力法实现 indexOf() 方法，其中有很多无效计算
     * </p>
     *
     * @param haystack 源字符串
     * @param needle   匹配字符串
     * @return int       匹配的初始位置
     * @throws
     * @author Eric
     * @date 2019/5/22
     **/
    public int indexOf(String haystack, String needle) {
        if (needle.length() == 0) {
            return 0;
        }
        int needStart = 0;
        //for 循环每个位置开始匹配
        for (int i = 0; i + needStart < haystack.length(); i++) {
            //从首位开始比较
            while (i + needStart < haystack.length() && needStart < needle.length()) {
                if (haystack.charAt(i + needStart) == needle.charAt(needStart)) {
                    //匹配，则比较位置向后一位
                    needStart++;
                } else {
                    //不匹配，比较位置归零，跳出循环，i向后移动一位
                    needStart = 0;
                    break;
                }
            }
            //如果比较位置超过了，匹配字符长度，则是已经匹配到
            if (needStart >= needle.length()) {
                return i;
            }
        }
        //没有匹配到返回-1
        return -1;
    }


    /**
     * @param haystack 源字符串
     * @param needle   匹配字符串
     * @return int
     * @throws
     * @author Eric
     * @date 2019/5/22
     **/
    public int kmpIndexOf(String haystack, String needle) {
        if (needle.length() == 0) {
            return 0;
        }
        int[] next = fastNext(needle);
        int p = 0;
        int i = 0;
        while (i < haystack.length()) {
            if (p == -1 || haystack.charAt(i) == needle.charAt(p)) {
                ++p;
                ++i;
            } else {
                p = next[p];
            }
            if (p >= needle.length()) {
                return i - p;
            }
        }
        return -1;
    }

    @Test
    public void testNext() {
        IndexOf indexOf=new IndexOf();
        Long start=System.currentTimeMillis();
        strList.forEach(k->{
            indexOf.next(k);
//            System.out.println(Arrays.toString(indexOf.next(k)));
        });
        Long end=System.currentTimeMillis();
        Long count=end-start;
        System.out.println("substring:" +count);

         start=System.currentTimeMillis();
        strList.forEach(k->{
            indexOf.smartNext(k);
//            System.out.println(Arrays.toString(indexOf.smartNext(k)));
        });
         end=System.currentTimeMillis();
         count=end-start;
        System.out.println("smart:" +count);

        start=System.currentTimeMillis();
        strList.forEach(k->{
            indexOf.fastNext(k);
//            System.out.println(Arrays.toString(indexOf.fastNext(k)));
        });
        end=System.currentTimeMillis();
        count=end-start;
        System.out.println("fast:" +count);

    }

    /**
     * <p>
     * 求出 匹配字符串得next函数
     *                 0  j=0
     * next()函数=     Max{k|0<k<j   , P1 P2 ...Pk=Pj-k+1 Pj-k+2}
     *                 1         其他情况
     * </p>
     *
     * @param needle 1
     * @return int[]
     * @throws
     * @author Eric
     * @date 2019/5/22
     **/
    public int[] next(String needle) {
        int[] arr = new int[needle.length() + 1];
        arr[0] = -1;
        for (int i = 0; i < needle.length(); i++) {
            int k = i;
            if (i == 0) {
                arr[i + 1] = 0;
            } else if (0 < k && k <= i) {
                while (k > 0) {
                    if (needle.substring(0, k).equals(needle.substring(i + 1 - k, i + 1))) {
                        arr[i + 1] = k;
                        break;
                    }
                    k--;
                }
            }
        }
        return arr;
    }

    /**
     * <p>
     * 优化后的 求next数组 方法
     * </p>
     *
     * @param needle 1
     * @return int[]
     * @throws
     * @author Eric
     * @date 2019/5/23
     **/
    public int[] smartNext(String needle) {
        int[] arr = new int[needle.length() + 1];
        arr[0] = -1;
        for (int i = 0; i < needle.length(); i++) {
            if (i == 0) {
                arr[i + 1] = 0;
            } else {
                arr[i + 1] = getK(needle, i);
            }
        }
        return arr;
    }
    /**
     * <p>
     *     求next 函数 最大k值
     * </p>
     * @author Eric
     * @date 2019/5/23
     * @param needle    字符串
     * @param i         字符串 偏移位置
     * @return int
     * @throws
     **/
    private int getK(String needle, int i) {
        for(int k=i;k>0;k--){
            for(int j=1;j<=k;j++){
                if(needle.charAt(k-j)!=needle.charAt(i+1-j)){
                    break;
                }
                if(j==k){
                    return k;
                }
            }
        }
        return 0;
    }

    /**
     * <p>
     *     百度到最优 next 求解
     * </p>
     * @author Eric
     * @date 2019/5/23
     * @param  needle 字符串
     * @return int[]
     * @throws
     **/
    public int [] fastNext(String needle){
        int len = needle.length();
        int [] next=new int[len+1];
        next[0]=-1;
        if(needle.length()==0){
            return next;
        }
        //初始化
        next[1]=0;
        for(int i=1,k=0;i<len;i++) {
            //这个while是最关键的部分
            while(k>0 && needle.charAt(k)!=needle.charAt(i)){
                k=next[k];
            }
            //等价于  k=next[next[i-1]-1]
            //等号右边的k起的只是下标的作用
            if(needle.charAt(k)==needle.charAt(i)){
                //相等就+1
                k++;
            }
            //赋值
            next[i+1]=k;
        }
        return next;
    }


    /**
     * <p>
     * BF 算法实现的 indexOf() 方法
     * 坏字符串概率
     * 移动量=匹配字符串出现坏树的时候 匹配字符串的下标-源字符串（坏字符串）在被匹配字符串再次出现的下表
     * A A A A A A becsdsddadadsd      A 坏字符串
     * |
     * b A b d d a
     * 偏移量=5-1       4
     * </p>
     *
     * @param hayStack 源字符串
     * @param needle   匹配字符串
     * @return int       匹配的初始位置
     * @throws
     * @author Eric
     * @date 2019/5/22
     **/
    public int bfIndexOf(String hayStack, String needle) {
        if (needle.length() == 0) {
            return 0;
        }
        //初始化长度
        int hLen = hayStack.length() - 1;
        //初始化长度
        int nLen = needle.length() - 1;
        //i  源字符串 偏移量
        int i = nLen;
        // 匹配字符串偏移量
        int index = nLen;
        while (i <= hLen) {
            // 源字符串向后匹配 偏移量
            int yd = i;
            while (index >= 0) {
                if (hayStack.charAt(yd) == needle.charAt(index)) {
                    //匹配成功 则向后匹配
                    yd--;
                    index--;
                    if (index < 0) {
                        return i - nLen;
                    }
                } else {
                    //匹配失败则是坏字符串，匹配坏字符串是否有匹配的
                    int match = -1;
                    //这里考虑能不能用内存优化，这样遍历很浪费时间
                    for (int j = index - 1; j >= 0; j--) {
                        if (hayStack.charAt(yd) == needle.charAt(j)) {
                            match = j;
                            break;
                        }
                    }
                    i += index - match;
                    index = nLen;
                    break;
                }
            }
        }
        return index < 0 ? i - nLen : -1;
    }

    /**
     * <p>
     * 遍历方式获取到 前面和坏数匹配的下标
     * 调用该方法后，相对方法内容嵌入慢1ms
     * 所以这里不调用该方法
     * </p>
     *
     * @param badString 坏字符
     * @param needle    匹配字符串
     * @param index     匹配字符偏移位
     * @return int
     * @throws
     * @author Eric
     * @date 2019/5/22
     **/
    private int getMatch(char badString, String needle, int index) {
        int match = -1;
        //这里考虑能不能用内存优化，这样遍历很浪费时间
        for (int j = index - 1; j >= 0; j--) {
            if (badString == needle.charAt(j)) {
                match = j;
                break;
            }
        }
        return match;
    }


    private Map<String, Map<Character, List<Integer>>> match = new HashMap<>(16);

    /**
     * <p>
     * map 优化后 前面和坏数匹配的下标
     * 尝试了，优化后  得不偿失，感觉没多大作用，运行时间还边长了
     * 所以不调用该方法
     * </p>
     *
     * @param badString 坏字符
     * @param needle    匹配字符串
     * @param index     匹配字符偏移位
     * @return int
     * @throws
     * @author Eric
     * @date 2019/5/22
     **/
    private int getMapMatch(char badString, String needle, int index) {
        Map<Character, List<Integer>> map = match.get(needle);
        if (map == null) {
            map = new HashMap<>(16);
            for (int i = 0; i < needle.length(); i++) {
                Character ch = needle.charAt(i);
                if (map.get(ch) == null) {
                    List<Integer> arr = new ArrayList<>();
                    arr.add(i);
                    map.put(ch, arr);
                } else {
                    map.get(ch).add(i);
                }
            }
            match.put(needle, map);
        }
        if (map.get(badString) == null) {
            return -1;
        }
        List<Integer> list = map.get(badString);
        for (int i = list.size() - 1; i >= 0; i--) {
            if (list.get(i) < index) {
                return list.get(i);
            }
        }
        return -1;

    }


}
